class Solution:
    def productExceptSelf(self, nums):
        result = [None] * len(nums)
        self.product(nums, result, 0, len(nums), 1)
        return result

    def product(self, nums, result, start, end, pre):
        if start+1 == end:
            result[start] = pre
            return
        mid = (start + end)//2
        preProduct = pre
        for i in range(start, mid):
            preProduct = preProduct*nums[i]
        prefixProduct = pre
        for i in range(mid, end):
            prefixProduct = prefixProduct*nums[i]
        self.product(nums, result, start, mid, prefixProduct)
        self.product(nums, result, mid, end, preProduct)

if __name__ == '__main__':
    so = Solution()
    s = [1,2,3,4]
    r = so.productExceptSelf(s)
    print(r)
